package algorithm.Sort;

import java.io.*;

/**
 * 峰值问题可以用二分查找解决
 * 峰值问题是指在一个规模为n的数组中，任意两个相邻的元素不相等，且为无序数组
 * 而峰值是指比左右两个相邻的元素都大的元素对应的值
 * 特殊的，如果是左边界和右边界，只要比右边（左边）相邻的元素值大即为峰值
 * 将问题简化为：若有多个峰值，只需要返回其中一个峰值。
 */
public class PeakValue {

    public static int MAX_SIZE=1001;
    public static int[] arr=new int[MAX_SIZE];


    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in=new StreamTokenizer(br);
        PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
        int i=0;
        while(in.nval!=StreamTokenizer.TT_EOF){
            arr[i]=(int)in.nval;
            i++;
            in.nextToken();
        }
        out.println(findPeakElement());
        out.flush();
        br.close();
        out.close();
    }

    //测试在leetcode 162寻找峰值
    public static int findPeakElement() {

        int n = arr.length;
        if (n == 1) return 0;
        if (arr[0] > arr[1]) return 0;
        if (arr[n - 1] > arr[n - 2]) return n - 1;

        int l = 1, r = n - 2, m = 0;
        int ans = -1;
        while (l <= r) {
            m = (l + r) / 2;
            if (arr[m - 1] > arr[m]) {
                r = m - 1;
            } else if (arr[m + 1] > arr[m]) {
                l = m + 1;
            } else {
                //这里的else是指m为峰值点，即左边和右边的相邻元素都没m大
                ans = m;
                break;
            }
        }
        return ans;
    }
}
